#include<iostream>
#include<string>
using namespace std;
#include<algorithm>

int dp[550][550];

class Solution {
public:
    int minDistance(string word1, string word2) {
        // return recursion(word1, word2, word1.length(), word2.length());
        return dpPlan(word1, word2);
    }
    //递归
    /**
     * word1:字符串1
     * word2:字符串2
     * len1:word1字符串长度
     * len2:word2字符串长度
     * 返回word1编辑为word2需要花费的代价
    */
    int recursion(const string& word1, const string& word2, int len1, int len2) {
        if(len1 == 0) {
            //插入word2
            return len2;
        } else if(len2 == 0) {
            //删除word1
            return len1;
        } else if(word1[len1 - 1] == word2[len2 - 1]) {
            return recursion(word1, word2, len1-1, len2-1);
        } else {
            //word1尾部插入word2[len2 - 1]
            int r1 = recursion(word1, word2, len1, len2-1) + 1;
            //word1尾部删除word1[len1 - 1]
            int r2 = recursion(word1, word2, len1-1, len2) + 1;
            //word1尾部替换为word[len2 - 1]
            int r3 = recursion(word1, word2, len1-1, len2-1) + 1;
            //取最少代价方案数
            return min(r1, min(r2, r3));
        }
    }

    //动态规划
    int dpPlan(const string& word1, const string& word2) {
        //dp[i][j] word1的前i个字符 编辑为 word2的前j个字符需要的代价
        int len1 = word1.length();
        int len2 = word2.length();
        //word2 为空串
        for(int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        //word1 为空串
        for(int i = 0; i <= len2; i++) {
            dp[0][i] = i;
        }
        //补充矩阵其余部分
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                if(word1[i-1] == word2[j-1]) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    int r1 = dp[i-1][j] + 1;
                    int r2 = dp[i][j-1] + 1;
                    int r3 = dp[i-1][j-1] + 1;
                    dp[i][j] = min(r1,min(r2,r3));
                }
            }
        }
        return dp[len1][len2];
    }
};

int main() {
    int ret = Solution().minDistance("horse","ros");
    cout << ret << endl;
    return 0;
}